package com.cqs.leetcode.dp;

import com.cqs.leetcode.TestCaseUtils;

import java.util.*;

/**
 * Created by li on 19-12-22.
 */
public class PartitionEqualSubsetSum416 {


    static class Solution2 {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            //和为奇数，肯定不能分割为两个和相等的子集
            if (sum % 2 != 0) {
                return false;
            }
            sum /= 2;

            //将数组做降序排序，是为了可以进行剪支，避免无用的查找
            Arrays.sort(nums);
            reverse(nums);

            return canPartition(nums, sum, 0);
        }

        //翻转数组
        public static void reverse(int[] data) {
            for (int left = 0, right = data.length - 1; left < right; left++, right--) {
                // swap the values at the left and right indices
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
            }
        }

        boolean canPartition(int[] nums, int sum, int index, int target) {
            if (sum == target) return true;
            if (sum > target) return false;
            if (index >= nums.length) return false;
            return canPartition(nums, sum + nums[index], index + 1, target) || canPartition(nums, sum, index + 1, target);
        }

        private boolean canPartition(int[] nums, int sum, int index) {
            if (index >= nums.length || nums[index] > sum) {
                return false;
            }
            if (nums[index] == sum) {
                return true;
            }
            //对于数组每个元素，都有选择和不选择两种可能。
            return canPartition(nums, sum - nums[index], index + 1) || canPartition(nums, sum, index + 1);
        }
    }


    static class Solution0 {

        //        Set<String> prefix = new HashSet<>();
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 0) return false;
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
//            return (sum & 1) == 0 && canPartition(nums, 0, 0, sum >> 1);
            return (sum & 1) == 0 && canPartition(nums, new boolean[nums.length], 0, sum >> 1);
        }

        boolean canPartition(int[] nums, int sum, int index, int target) {
            if (sum == target) return true;
            if (sum > target) return false;
            if (index >= nums.length) return false;
            return canPartition(nums, sum + nums[index], index + 1, target) || canPartition(nums, sum, index + 1, target);
        }

        boolean canPartition(int[] nums, boolean[] used, int sum, int target) {
            if (target == sum) return true;
            if (sum > target) return false;
            //boolean[] levelUsed =new  boolean[nums.length];
            //剪枝
            Set<Integer> handle = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
                if (!used[i] && !handle.contains(nums[i])) {
                    used[i] = true;
                    handle.add(nums[i]);
                    boolean succ = canPartition(nums, used, sum + nums[i], target);
                    if (succ) return true;
                    used[i] = false;
                }
            }
            return false;
        }
    }


    static class Solution {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 0) return false;
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            //奇数
            if ((sum & 1) == 1) return false;
            int target = sum >> 1;
            sum = 0;
            boolean[] results = new boolean[100 * 200 + 1];
            results[0] = true;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                //必须从大到小遍历 case [ 2 2 3 5] 若从小到大 那么results[6] == true
                for (int j = sum; j >= nums[i]; --j) {
                    //results[j]可能又前面的计算为true
                    results[j] = results[j] | results[j - nums[i]];
                    //优化 提前终止
                    if (results[target]) return true;
                }
            }
            return results[sum >> 1];
        }
    }

    static class Solution1 {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length <= 0) return false;
            boolean[] results = new boolean[100 * 200 + 1];
            results[0] = true;
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                //必须从大到小遍历 case [ 2 2 3 5] 若从小到大 那么results[6] == true
                for (int j = sum; j >= nums[i]; --j) {
                    //results[j]可能又前面的计算为true
                    results[j] = results[j] | results[j - nums[i]];
                }
            }
            //奇数
            if ((sum & 1) == 1) return false;
            return results[sum >> 1];
        }
    }

    static class Solution3 {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            if (sum % 2 == 1) return false;
            int target = sum / 2;
            boolean[][] dp = new boolean[nums.length][target + 1];
            for (int i = 0; i < nums.length; ++i) {
                dp[i][0] = true;
                for (int j = 1; j <= target && i > 0; ++j) {
                    dp[i][j] = dp[i - 1][j];
                    if (!dp[i][j] && j >= nums[i]) {
                        dp[i][j] = dp[i - 1][j - nums[i]];
                    }
                }
                if (nums[i] <= target) dp[0][nums[i]] = true;
                if (dp[i][target]) return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        Solution2 s0 = new Solution2();
        Solution3 s3 = new Solution3();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1; i++) {
//            int[] testCase = TestCaseUtils.randomArr(100, 201);
//            int[] testCase = new int[]{1,1,1,1,1,1,8};
            //int[] testCase = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 100};
//            int[] testCase = new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100};
            int[] testCase = new int[]{3, 3, 3, 4, 5};
            boolean result2 = s3.canPartition(testCase);
            boolean result = s.canPartition(testCase);
            boolean result0 = s0.canPartition(testCase);
            new Solution0().canPartition(testCase);
            System.out.println(TestCaseUtils.arrFormat(testCase) + "\t" + result + "\tresult2:" + result2);
            if (result != result0) {
                System.err.println(result + "\t" + result0);
                throw new RuntimeException();
            }
        }
        System.out.println(System.currentTimeMillis() - start);
    }
}
